perm filename A31.TEX[106,RWF] blob sn#872423 filedate 1989-04-21 generic text, type C, neo UTF8
COMMENT āŠ—   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
CāŠ—;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a31.tex[106,phy] \today\hfill}

\bigskip
{\rmn
{\narrower\smallskip\noindent
{\bf Exercise.}

\noindent
The diagrams below show several orders in which a program might process
some of the elements of an array, perhaps by reading into them or
printing them. For example, according to the second diagram the
program is to do something successively to $A[1,1],A[2,1],A[2,2]$,
$A[3,1],\ldots,A[5,5]$.
For each diagram, find a driver that executes
command~$S$ repeatedly, giving $R$ and~$C$ values such that when~$S$
is executed $A[R,C]$ is the correct array element for it to process.
\smallskip}
}

$$\vbox{\offinterlineskip
\halign{\hfil#\hfil\qquad&\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad&\vrule#\cr
&&\omit&1&2&3&4&5\cr
\noalign{\smallskip}
&&\multispan6\hrulefill\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
(1)&1&&1&&&&&\cr
&2&&2&3&&&&\cr
&3&&4&5&6&&&\cr
&4&&7&8&9&10&&\cr
&5&&11&12&13&14&15&\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
&&\multispan6\hrulefill\cr}}
\qquad\qquad
\vbox{\offinterlineskip
\halign{\hfil#\hfil\qquad&\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad&\vrule#\cr
&&\omit&1&2&3&4&5\cr
\noalign{\smallskip}
&&\multispan6\hrulefill\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
(2)&1&&1&2&3&4&5&\cr
&2&&10&9&8&7&6&\cr
&3&&11&12&13&14&15&\cr
&4&&20&19&18&17&16&\cr
&5&&21&22&23&24&25&\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
&&\multispan6\hrulefill\cr
}}$$

$$\vbox{\offinterlineskip
\halign{\hfil#\hfil\quad&\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad&\vrule#\cr
&&\omit&1&2&3&4&5&6&7&8&9\cr
\noalign{\smallskip}
&&\multispan{10}\hrulefill\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
(3)&1&&&&&&1&&&&&\cr
&2&&&&&4&3&2&&&&\cr
&3&&&&5&6&7&8&9&&&\cr
&4&&&16&15&146&13&12&11&10&&\cr
&5&&17&18&19&20&21&22&23&24&25&\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
&&\multispan{10}\hrulefill\cr
}}
\qquad
\vbox{\offinterlineskip
\halign{\hfil#\hfil\quad&\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad&\vrule#\cr
&&\omit&1&2&3&4&5\cr
\noalign{\smallskip}
&&\multispan6\hrulefill\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
(4)&1&&1&2&3&4&5&\cr
&2&&16&17&18&19&6&\cr
&3&&15&24&25&20&7&\cr
&4&&14&23&22&21&8&\cr
&5&&13&12&11&10&9&\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
&&\multispan6\hrulefill\cr
}}$$


\bigskip
{\rmn
{\narrower\smallskip\noindent
{\bf Solution.}

\noindent
{\obeylines\obeyspaces\let =\ \tt
{\rm(1)}     R:=1; C:=1;
        WHILE R<6 DO
            BEGIN
            S;
            IF C=R THEN
                BEGIN
                C:=1;
                R:=R+1
                END
            ELSE C:=C+1
            END
}

\vfill\eject

\noindent
{\obeylines\obeyspaces\let =\ \tt
{\rm(2)}     R:=1; C:=1; STEP:=1;
        FOR I:=1 TO 25 DO
            BEGIN
            S;
            IF I MOD 5=0 THEN
                BEGIN
                R:=R+1;
                STEP:=-STEP
                END
            ELSE C:=C+STEP
            END
}

\noindent
{\obeylines\obeyspaces\let =\ \tt
{\rm(3)}     C:=5; STEP:=1;
        FOR R:=1 TO 5 DO
            BEGIN
            FOR I:=1 TO 2*R-1 DO
                BEGIN
                S;
                C:=C+STEP;
                END;
            STEP:=-STEP
            END
}

\noindent
{\obeylines\obeyspaces\let =\ \tt
{\rm(4)}     BEGIN
        R:=1; C:=1; LENGTH:=4; RSTEP:=0; CSTEP:=1;
        WHILE LENGTH>0 DO
            BEGIN
            FOR DIRECTION:=1 TO 4 DO
                BEGIN
                FOR COUNT:=1 TO LENGTH DO
                    BEGIN
                    S;
                    R:=R+RSTEP; C:=C+CSTEP;
                    END;
                TEMP:=-RSTEP; RSTEP:=CSTEP; CSTEP:=TEMP;
                END;
            LENGTH:=LENGTH-2;
            R:=R+1; C:=C+1;
            END;
        S (* CENTER IS AN EXCEPTION *)
        END
}
\smallskip}
}

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\bye